package main

import "fmt"

// 如何求两个有序集合的交集

func main() {
	l1 := []*mySet{
		{min: 4, max: 8},
		{min: 9, max: 13},
	}
	l2 := []*mySet{
		{min: 6, max: 12},
	}
	result := getIntersection(l1, l2)
	for _, v := range result {
		fmt.Println("[", v.min, ",", v.max, "]")
	}
}

type mySet struct {
	min int
	max int
}

func getIntersection(l1, l2 []*mySet) []*mySet {
	result := make([]*mySet, 0)
	for i, j := 0, 0; i < len(l1) && j < len(l2); {
		s1 := l1[i]
		s2 := l2[j]
		if s1.min < s2.min {
			if s1.max < s2.min {
				i++
			} else if s1.max <= s2.max {
				result = append(result, &mySet{s2.min, s1.max})
				i++
			} else {
				result = append(result, &mySet{s2.min, s2.max})
				j++
			}
		} else if s1.max <= s2.max {
			result = append(result, &mySet{min: s1.min, max: s1.max})
			i++
		} else if s1.min <= s2.max {
			result = append(result, &mySet{min: s1.min, max: s2.max})
			j++
		} else {
			j++
		}
	}

	return result
}
